//
// Description: Floyd算法模板
// Created by Loading on 2021/8/17.
//

/* 适用于在带权有向图中求解任意两点之间的最短路径，注意：图中不能存在负权回路，因为这样将不存在最短路 */
/* 时间复杂度：O(n^3)，n 表示节点个数，适用于 n 较小的情况，一般 n <= 100 */

#include <bits/stdc++.h>

using namespace std;

const int n = 100;
// 认定的极大值
const int INF = 0x3f3f3f3f;
// d[i][j] 表示从 i 到 j 之间的最短路长度
int d[n + 1][n + 1];

// 初始化
void init() {
    // d[i][i] 初始化为 0，d[i][j] 初始化为极大值
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                d[i][j] = 0;
            } else {
                d[i][j] = INF;
            }
        }
    }
}

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

int main() {

}